# -*- coding:utf-8 -*-
import hashlib
import random

class MerkleTree:
    def __init__(self, data_list):
        self.data_list = data_list  # 初始化Merkle树，传入数据列表
        self._merkle_tree = dict()
        self.hash_list = self.list_hashing(data_list)
        (self.hash_list, self.layer_length) = self.generate(self.hash_list)  # 生成Merkle树
        self._merkle_root = self.hash_list["layer_{}".format(len(self.hash_list) - 1)]  # 获取Merkle根

    def list_hashing(self, data_list):
        # 对数据列表进行哈希处理
        result_hash_list = list()
        for data in data_list:
            sha_256 = hashlib.sha256()
            sha_256.update(data.encode('utf-8'))
            result_hash_list.append(sha_256.hexdigest())
        return result_hash_list

    def catenate_hash(self, data1, data2):
        # 对两个数据进行哈希处理
        sha_256 = hashlib.sha256()
        sha_256.update(data1.encode('utf-8'))
        sha_256.update(data2.encode('utf-8'))
        return sha_256.hexdigest()

    def generate(self, hash_list):
        # 生成Merkle树
        mt = dict()
        layer_count = 0
        layer_list = hash_list
        while len(layer_list) > 1:
            mt["layer_{}".format(layer_count)] = layer_list
            layer_count += 1
            next_layer_list = list()
            pair_num = len(layer_list) // 2
            for i in range(pair_num):
                next_layer_list.append(self.catenate_hash(layer_list[i * 2], layer_list[i * 2 + 1]))
            if len(layer_list) % 2 == 1:
                next_layer_list.append(self.catenate_hash(layer_list[-1], layer_list[-1]))
            layer_list = next_layer_list
        mt["layer_{}".format(layer_count)] = layer_list
        return mt, layer_count

# 测试代码
data_list = ["交易_{}".format(i) for i in range(10)]
merkle_tree = MerkleTree(data_list)
print("Merkle树层数为: {}".format(merkle_tree.layer_length))
print("Merkle树的Top Hash节点值: {}".format(merkle_tree._merkle_root))